#include <iostream>
#include <limits.h>
#include <string.h>
int coinChange(int [], int, int, int []);
int coinChange(int coins[], int len, int target, int memo[])
{
    if (memo[target] != 0) return memo[target];
    if (target == 0) return 0;
    if (target < 0) return -1;

    int res = INT_MAX;
    for(int i = 0; i < len; i++)
    {
        int temp = coinChange(coins, len, target - coins[i], memo);
        if (temp == -1) continue;
        res = res < temp + 1 ? res : temp + 1;
    }
    memo[target] = res != INT_MAX ? res : -1;
    return memo[target];
}

int main()
{   
    using namespace std;
    int coins[3] = {1, 2, 5};
    int target = 11;
    int memo[target + 1];
    memset(memo, 0, sizeof(memo));
    cout << coinChange(coins, 3, target, memo) << endl;
    return 0;
}